//
//  lianbiao.cpp
//  shunxubiao
//
//  Created by 刘文栖 on 2017/8/5.
//  Copyright © 2017年 刘文栖. All rights reserved.
//

#include "lianbiao.hpp"
//创建链表
//1.有头结点
LinkList CreateList(LinkList &L){
    int x;
    L = new LNode;
    LinkList s, r;
    r = L;
    printf("请输入结点:");
    scanf("%d", &x);
    while (x != 9999) {
        s = new LNode;
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
//2.无头结点
LinkList CreateList2(LinkList &L){
    int x;
    LinkList s, r;
    printf("请输入结点:");
    scanf("%d", &x);
    s = new LNode;
    s->data = x;
    r = L = s;//L得是s
    while (true) {
        scanf("%d", &x);
        if (x == 9999) {
            break;
        }
        s = new LNode;
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return L;
}

//打印当前链表
void PrintList(LinkList L){
    printf("\n当前链表为:");
    L = L->next;//包含头结点
    while (L) {//L不为NULL且L->next存在
        printf("%d\n", L->data);
        L=L->next;
    }
}
void PrintList2(LinkList L){//不包含头结点
    printf("\n当前链表为2:");
    while (L) {//L不为NULL且L->next存在
        printf("%d\n", L->data);
        L=L->next;
    }
}

//删除值为x的节点，不带头结点
void Del_x_3(LinkList &L, int x){
    LinkList p;
    if (L == NULL) {
        return ;
    }
    if (L->data == x) {
        p = L;
        L = L->next;
        delete p;
        Del_x_3(L, x);
    } else {
        Del_x_3(L->next, x);
    }
}

//删除值为x的结点，并释放其空间，x不唯一，且链表带头结点
void Del_x_1(LinkList &L, int x){
    if (L == NULL) return ;
    LinkList pre = L;
    LinkList p = L->next;
    LinkList q;//为了优雅的删除
    while (p) {
        if (p->data == x) {
            q = p;
            p = p->next;
            delete q;
            pre->next = p;
        } else {
            pre = p;
            p = p->next;
        }
    }
}
//删除值为x的结点，并释放其空间，x不唯一，且链表带头结点，采用尾插法
void Del_x_2(LinkList &L, int x){
    if (L == NULL) return ;
    LinkList r = L;
    LinkList p = L->next;//指向第一个结点
    r->next = NULL;
    LinkList q;//为了优雅的删除
    while (p) {
        if (p->data == x) {
            q = p;
            p = p->next;
            delete q;
        } else {
            r->next = p;
            r = p;//这里千万要注意
            p = p->next;
        }
    }
    r->next = NULL;
}
